package com.nowcoder.面试高频top202;

/**
 * @Description: 牛群的重新排序
 * @author： yeswater
 * @create： 2024/6/14
 */

public class NB4 {
	
	private class ListNode{
		int val;
		ListNode next = null;
		public ListNode(int val) {
			this.val = val;
		}
	}
	
	class solution {
		public ListNode reverseKGroup(ListNode head, int k) {
			ListNode dummy = new ListNode(0);
			dummy.next = head;
			
			ListNode pre = dummy;
			ListNode cur = head;
			
			int count = 0;
			while (cur != null) {
				count++;
				if (count % k == 0) {
					pre = reverse(pre, cur.next);
					cur = pre.next;
				} else {
					cur = cur.next;
				}
			}
			return dummy.next;
		}
		
		private ListNode reverse(ListNode pre, ListNode end) {
			ListNode cur = pre.next;
			ListNode tail = cur;
			
			while (cur != end) {
				ListNode temp = cur.next;
				cur.next = pre.next;
				pre.next = cur;
				cur = temp;
			}
			
			tail.next = end;
			return tail;
		}
	}
}
